
public class Resolver {
	private int[][] data;
	private ResultListener listener;
	private int machines; // ilosc
	private int tasks; // ilosc
	private int[] current; // aktualna permutacja
	private int[] best; // najlepsza permutacja
	private boolean[] occupied; // pomocna do permutacji
	private int[][] endingTimes; // czasy od poczatku do zakonczenia zadania na danej maszynie
								// dostep: endingTimes[zadanie][maszyna] - zadania wg kolejnosci w permutacji, nie wg kolejnosci z data
	private int bestTime; // calkowity czas najlepszej permutacji
	
	public Resolver(int[][] d, ResultListener l) {
		data = d;
		listener = l;
		machines = d[0].length;
		tasks = d.length;
		current = new int[tasks];
		best = new int[tasks];
		occupied = new boolean[tasks];
		for (int i = 0; i < tasks; i++)
			occupied[i] = false;
		bestTime = Integer.MAX_VALUE;
		endingTimes = new int[tasks][machines];
	}
	
	public void resolve() {
		permutate(0);
	}
	
	private void permutate(int index) {
		if (index == tasks) { // gdy kompletna permutacja
			int total = computeTotalTime(); 
			if (total < bestTime) { // czy nowa najlepsza
				bestTime = total;
				listener.newResult(current, total); // powiadom o nowym rozwiazaniu
				best = current.clone();
			}
		} else {
			for (int i = 0; i < tasks; i++) { // wyznacz kolejny element permutacji
				if (!occupied[i]) {
					occupied[i] = true;
					current[index] = i;
					permutate(index + 1);
					occupied[i] = false;
				}
			}
		}
	}
	
	private int computeTotalTime() {
		// wyzeruj czasy zakonczenia
		for (int i = 0; i < tasks; i++)
			for (int j = 0; j < machines; j++)
				endingTimes[i][j] = 0;
		// zwroc czas zakonczenia ostatniego zadania na ostatniej maszynie
		return getEndingTime(tasks - 1, machines - 1);
	}
	
	private int getEndingTime(int task, int machine) {
		//System.out.println(String.format("ET: %d %d", task, machine));
		if (endingTimes[task][machine] != 0) // gdy juz jest obliczony
			return endingTimes[task][machine];
		else {
			int thisTaskOnPrevMachineET = 0;
			int prevTaskOnThisMachineET = 0;
			if (task != 0) // czy nie pierwsze zadanie
				prevTaskOnThisMachineET = getEndingTime(task - 1, machine);
			if (machine != 0) // czy nie pierwsza maszyna
				thisTaskOnPrevMachineET = getEndingTime(task, machine - 1);
			// dane zadanie zacznie sie wykonywac na danej maszynie gdy
			// - skonczy sie poprzednie na tej maszynie
			// - aktualne zakonczy sie na poprzedniej maszynie
			// czas zakonczenia pozniejszego z powyzszych jest czasem
			// rozpoczecia
			endingTimes[task][machine] = Math.max(prevTaskOnThisMachineET,
					thisTaskOnPrevMachineET) + data[current[task]][machine];
			return endingTimes[task][machine];
		}
	}
	
	public int[] getBest() {
		return best;
	}
	
	public int getBestTime() {
		return bestTime;
	}
}
